package main

import (
	"container/heap"
	"fmt"
)

type myHeap [][2]int

func (h *myHeap) Push(x interface{}) {
	*h = append(*h, x.([2]int))
}

func (h *myHeap) Pop() interface{} {
	top := (*h)[len(*h)-1]
	*h = (*h)[:len(*h)-1]
	return top
}

func (h *myHeap) Len() int {
	return len(*h)
}

func (h *myHeap) Less(i, j int) bool {
	return (*h)[i][1] > (*h)[j][1]
}

func (h *myHeap) Swap(i, j int) {
	(*h)[i], (*h)[j] = (*h)[j], (*h)[i]
}

func maxSlidingWindow(nums []int, k int) []int {
	var result []int
	h0 := make(myHeap, 0)
	heap.Init(&h0)
	for i, v := range nums {
		heap.Push(&h0, [2]int{i, v})
		if i < k-1 {
			continue
		}
		min := i + 1 - k
		if min < 0 {
			min = 0
		}
		var top [2]int
		for {
			top = h0[0]
			if top[0] < min {
				heap.Pop(&h0)
				continue
			}
			break
		}
		result = append(result, top[1])
	}
	return result
}

func main() {
	ret := maxSlidingWindow([]int{1, -1}, 1)
	fmt.Printf("%#v\n", ret)
	ret = maxSlidingWindow([]int{1, 3, -1, -3, 5, 3, 6, 7}, 3)
	fmt.Printf("%#v\n", ret)
}
